// Package day_11_slider_window_monotone_stack demo-02
// @Title day_11_slider_window_monotone_stack
// @Description  派对的最大快乐值
// @Author  == 琳琳也叫王木木 ==  2021/9/4 19:15
// @Create  2021/9/4 19:15
package day_11_slider_window_monotone_stack

/**
公司每个员工都有符合Employee 类的描述，整个公司人员结构可以看做是颗标准的，没有环的多叉树
树的头结点是公司唯一的老板，除老板之外的每个员工都有唯一的上级，

公司现在要举办party，你可以决定哪些员工来，哪些员工不来，但是：
1. 如果某个员工来了，那么这个员工的所有直接下级都不能来
2. 排队的整体快乐值是所有到场员工的快乐值累加
3. 你的目标是让这个party的快乐值尽量大

给你员工树的boss节点，返回整体快乐的最大值
*/

// Employee 员工信息结构体
type Employee struct {
	Happy        int         // 员工带来的快乐值
	Subordinates []*Employee // 这名员工有哪些直接下级
}

/**
思路：
x节点的最大快乐值是多少？
1. x参与？
x(乐) + 直接下级的整棵树-直接下级的快乐值

2. x不参与
0+ 所有直接下级参加的时候的快乐值和不来的时候快乐值的max
*/
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// 递归函数返回值结构
type HappyInfo struct {
	JoinMax   int // 参与时候的最大值
	NoJoinMax int // 不参与的时候的最大值
}

func process2(root *Employee) HappyInfo {
	if len(root.Subordinates) < 1 {
		return HappyInfo{root.Happy, 0}
	}
	joinMax := root.Happy // x 来的情况下，整棵树的最大快乐值
	noJoin := 0           // x不来的情况下，x整棵树的最大受益
	for i := 0; i < len(root.Subordinates); i++ {
		infos := process2(root.Subordinates[i])
		joinMax += infos.NoJoinMax
		noJoin += max(infos.JoinMax, infos.NoJoinMax)
	}
	return HappyInfo{joinMax, noJoin}
}

// MaxHappyParty 获取员工party的最大值之和
func MaxHappyParty(root *Employee) int {
	res := process2(root)
	return max(res.NoJoinMax, res.JoinMax)
}
